package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    // 时时想着这是一颗树
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为null, 那么直接返回null
        if (root == null) return null;
        // 如果左节点为的值即为其中一个值, 那么它就是这个他们的公共节点
        if (root.val == p.val || root.val == q.val) return root;
        // 从这颗树的左节点找到这个p节点, 并且这颗树的左节点找到了q节点
        // 那么说明p与q都同时在root的同一侧
        if (find(root.left, p) && find(root.left, q)) {
            // 那么再以root的左节点为根节点进行递归
            return lowestCommonAncestor(root.left, p, q);
        }
        // 从这颗树的右节点中找到p与q
        // 那么说明q与p都同时在root的右侧
        if (find(root.right, p) && find(root.right, q)) {
            // 递归进行搜索
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
    // 一直接去这个节点下去找这个节点
    private boolean find(TreeNode root, TreeNode c) {
        // 如果这个节点为null, 那么肯定是没有c节点了
        if (root == null) return false;
        if (root.val == c.val) {
            // 如果root就是要找的这个节点, 那么返回true
            return true;
        }
        // 再到它的左右节点去找
        return find(root.left, c) || find(root.right, c);
    }

    private static int times = 0;
    private static Map<Long, Long> map = new HashMap<>();
    public long fb(long n) {
        if (times ++ < Long.MAX_VALUE && map.containsKey(n)) {
            return map.get(n);
        }
        if (n == 0 || n == 1) {
            map.put(n, n);
            return n;
        }
        long l = fb(n - 1) + fb(n - 2);
        map.put(n, l);
        return l;
    }

    public long fb1(long n) {
        map.put(0L, 0L);
        map.put(1L, 1L);
        for (long i = 2; i <= n; i++) {
            map.put(i, map.get(i - 1) + map.get(i - 2));
        }
        return map.get(n);
    }

    public int kna(int[] w, int[] v, int c) {
        // 一个物品必须有一个重量嘛, 所以w与n的大小必须是一样的
        // w是重量, v是价值
        if (w.length != v.length) return 0;
        int size = w.length - 1;
        if (size == 0) return 0;
        Map<Integer, Integer> count = new HashMap<>();
        int[][] mm = new int[size][c];
        for(int j = 0; j<=c;j++) {
            // 第一层, 也就是只有第一个物品
            // 那么背包的容量, 得装得下这个物品
            // j是当前背包的容量, 只有当背包的容量大于第一物品的重量时, 才会放入, 否则是不会放入的
            // j当前背包的容量, v[0]是第一个物品的价值, 否则不放入, 那么价值为0
            mm[0][j] = j>=w[0]?v[0]:0;
        }

        for (int i = 1; i <= size; i++) {
            // 第i行, 有多少行, 代表有多少个物品
            for (int j = 0; j <= c; j++) {
                // 上一行能装什么, 这一行它还是能装什么
                mm[i][j] = mm[i - 1][j];
                // 如果现在的容量比这次的物品的大
                if (j >= w[i]) {
                    mm[i][j] = Math.max(mm[i][j], v[i] + mm[i - 1][j - w[i]]);
                }
            }
        }
        return mm[size][c];
    }

    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        Solution s = new Solution();
        System.err.println(s.fb(400));
        System.err.println("2121778230729308891");
        System.err.println("time = " + (System.currentTimeMillis() - l)+";times=" + times);
    }
}